package toOffer;

/**
 * @author YuanAo
 * @date 2024/7/4 10:21
 * @description 删除链表中的重复元素II
 */

import java.util.Arrays;

/**
 * 题目：
 * 给定一个已排序的链表的头 head ， 删除原始链表中所有重复数字的节点，只留下不同的数字 。返回 已排序的链表 。
 * <p>
 * 例子：
 * 输入：head = [1,2,3,3,4,4,5] 输出：[1,2,5]
 */
public class No82 {
    public static void main(String[] args) {
        int[] arr = {1, 1};

        ListNode dummy = new ListNode();
        final ListNode[] current = {dummy};

        Arrays.stream(arr).forEach(o -> {
            current[0].next = new ListNode(o);
            current[0] = current[0].next;
        });

        ListNode listNode = dummy.next;
        ListNode head = deleteDuplicates(listNode);
        while (head != null) {
            System.out.print(head.val + " ");
            head = head.next;
        }
    }

    /**
     * 思路：
     * （1）其实相当于有3个指针：
     * 第一个指针是用来选择是不是要把当前节点添加进链表；
     * 第二个指针是和第三个指针对照看的，看这两个指针的val值是否相等；
     * 相等就说明重复、就要找第三个指针的下一个节点，这个时候就是第二个指针指向第三个指针的下一个节点、第三个指针指向下一个节点的下一个节点
     *
     *
     * @param head
     * @return
     */
    public static ListNode deleteDuplicates(ListNode head) {
        // head为空、head的长度为1的都直接返回head
        if (head == null) {
            return head;
        }

        ListNode dummyNode = new ListNode();
        dummyNode.next = head;

        ListNode curNode = dummyNode;
        // 链表的节点数>=2
        while (curNode.next != null && curNode.next.next != null){
            if (curNode.next.val == curNode.next.next.val){
                int val = curNode.next.val;
                // 左指针节点不能为空 并且左指针节点的val值再相等 就继续往链表后面走
                while (curNode.next != null && curNode.next.val == val){
                    curNode.next = curNode.next.next;
                }
            }else {
                curNode = curNode.next;
            }
        }

        return dummyNode.next;
    }

    public static class ListNode {
        int val;
        ListNode next;

        ListNode() {
        }

        ListNode(int val) {
            this.val = val;
        }

        ListNode(int val, ListNode next) {
            this.val = val;
            this.next = next;
        }
    }
}
